package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/9/1.<br><br>
 *
 * 中等：Pow(x, n)
 */
public class Topic50 {

    public static void main(String[] args) {
        Topic50 instance = new Topic50();

        System.out.println(instance.myPow(2.0, 10));
        System.out.println(instance.myPow(2.1, 3));
        System.out.println(instance.myPow(2.0, -2));
    }

    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? helper(x, N) : 1 / helper(x, -N);
    }

    private double helper(double x, long N) {
        if(N == 0) {
            return 1;
        }

        double result = 1;
        double temp = x;
        while (N > 0) {
            if((N & 1) == 1) {
                result *= temp;
            }

            temp *= temp;

            N = N / 2;
        }

        return result;
    }

    private double helper2(double x, long N) {
        if(N == 0) {
            return 1.0;
        }

        double y = helper2(x, N / 2);
        return (N & 1) == 0 ? y * y : y * y * x;
    }
}
